Hash Table
何謂HashTable：
雜湊表（Hash table，也叫哈希表），是根據Key 而直接查詢在記憶體儲存位置的資料結構也就是說，它通過計算出一個鍵值的函數，將所需查詢的數據映射到表中一個位置來讓人查詢，這加快了查找速度。這個映射函數稱做雜湊函數(Ｈash Function)，存放記錄的數組稱做雜湊表
Hash Function_1 Division Function
info
m = HashTable size
n = number elements store in the hashTable
Index = Key mod m
以下面這個例子來看：
m = 5 (HashTable size)
n = 3 (Mike / Jason / Tim)
Index(Mike) = 123/5 = 24 ...3
Multiplication Method
- m = HashTable size
- n = number elements store in the hashTable
- Index = [ m ( key*A % 1 ) ]
- A = (√5-1) / 2
- 相較於 Division method，此種方法隨機性會比較大，Collision 出現的機率會來的比較小
Handling Collision
- 不論使用何種方法，一定會有 Collision
- 當 element 產生 Collision 時，使用陣列把 collision-elements 存取起來
實作如下：
Build hashTable
class Hashtable {
// m =hashtable size
constructor(size) {
this.size = size;
this.table = [];
for (let i = 0; i <= this.size; i++) {
this.table.push([]);
}
}
// division method
hash_1(key) {
return key % this.size;
}
// multiplication method
hash_2(key) {
const A = (Math.sqrt(5) - 1) / 2;
return Math.floor(this.size * ((key * A) % 1));
}
set(key, value) {
// value: Mike key: 11545
let index = this.hash_2(key);
this.table[index].push({ key, value });
}
get(key) {
const index = this.hash_2(key);
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i].key === key) {
return this.table[index][i];
}
}
}
printAll() {
console.log(this.table);
}
}
- 執行
let myHashTable = new Hashtable(6);
myHashTable.set(11424, "mike");
myHashTable.set(14, "tim");
myHashTable.set(113, "Jason");
myHashTable.printAll();
- 結果
[Running] node / Users / yenting / Documents / Algorithm / HashTable.js
# [Running] node "/Users/yenting/Documents/Algorithm/HashTable.js"
[
[],
[],
[ { key: 11424, value: 'mike' } ],
[ { key: 14, value: 'tim' } ],
[],
[ { key: 113, value: 'Jason' } ],
[]
]
[Done] exited with code=0 in 0.043 seconds
Hash keys are not number
info
接下來我們試著思考一個問題，如果HashTable的key不是數字我們該如何去處裡？
- The simplest (but not very effective) algorithm is to use the length of the string.(把 key 的長度當成數值)
- you could take the sum of all the ASCII values of all the characters in the string.(轉換成 ASCII code)
build parse function
parse(str) {
let result = 0;
for (let i = 0; i < str.length; i++) {
result = str.charCodeAt(i);
}
return result % this.size;
}
refactor hash_2
// multiplication method
hash_2(key) {
let parsedkey = typeof key !== "number" ? this.parse(key) : key;
const A = (Math.sqrt(5) - 1) / 2;
return Math.floor(this.size * ((parsedkey * A) % 1));
}
- 執行如下
myHashTable.set("white", "#FFFFFF");
myHashTable.set("magenta", "#FF00FF");
myHashTable.set("red", "#FF0000");
myHashTable.printAll();
[
[ { key: 'white', value: '#FFFFFF' } ],
[],
[ { key: 'red', value: '#FF0000' } ],
[ { key: 'magenta', value: '#FF00FF' } ],
[],
[],
[]
]